`
https://leetcode.cn/problems/sort-an-array/
`

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const temp = new Array(nums.length)

  const merge = (lo, mid, hi) => {
    // 先把 nums[lo..hi] 复制到辅助数组中
    // 以便合并后的结果能够直接存入 nums
    for (let i = lo; i <= hi; i++) {
      temp[i] = nums[i];
    }

    // 数组双指针技巧，合并两个有序数组
    let i = lo, j = mid + 1;
    for (let p = lo; p <= hi; p++) {
      if (i == mid + 1) {
        // 左半边数组已全部被合并
        nums[p] = temp[j++];
      } else if (j == hi + 1) {
        // 右半边数组已全部被合并
        nums[p] = temp[i++];
      } else if (temp[i] > temp[j]) {
        nums[p] = temp[j++];
      } else {
        nums[p] = temp[i++];
      }
    }
  }

  const sort = (lo, hi) => {
    // 单个元素不用排序
    if (lo === hi) return

    // 避免溢出，等同于 (lo + hi) / 2
    const mid = lo + ((hi - lo) >> 1)
    // 先对左半部分数组 nums[lo..mid] 排序
    sort(lo, mid)
    // 再对右半部分数组 nums[mid+1..hi] 排序
    sort(mid + 1, hi)
    // 将两部分有序数组合并成一个有序数组
    merge(lo, mid, hi)
  }

  sort(0, nums.length - 1)

  return nums
};